package org.lyc.dp;

/**
 * 打家劫舍
 * https://www.bilibili.com/video/BV1aa411f7uT?p=7&vd_source=65f5ad03ccd998407c9d802ca94f29fd
 * 一个专业的小偷,计划沿街偷窃.每个房间都藏有一定的现金和防盗系统, 如果两个相邻的房屋在同一晚被盗, 则会自动报警.
 * 要求在不触发报警的情况下, 一夜之间能偷取的最大金额
 * 输入 [1,2,3,1]
 * 输出 4
 * 偷取0和2
 * 输入 [2,7,9,3,1]
 * 输出 12
 * 偷取0,2,4
 *
 * @author Liu Yicong
 * @date 2024/1/31
 */
public class DRobHouse {
	static int[] gold = {9, 2, 7, 3, 1};

	public static void main(String[] args) {
		System.out.println(rob(gold));
	}

	public static int rob(int[] gold) {
		int length = gold.length;
		int[] dp = new int[length];
		dp[0] = gold[0];
		for (int i = 1; i < length; i++) {
			if (i == 1) {
				dp[1] = Math.max(gold[0], gold[1]);
			} else {
				dp[i] = Math.max(dp[i - 1], dp[i - 2] + gold[i]);
			}
		}
		return dp[gold.length - 1];
	}
}
